﻿// E. Number of k-good subarrays.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://codeforces.com/contest/1982/problem/E

让 bit(x) 表示非负整数 x 的二进制表示中 1 的个数。

一个数组的子数组如果只由不超过 k 的数组成，则称为 k
-好的数组。
 也就是说，如果数组 a 的子数组 (l,r) 满足条件 bit(ai)≤k 且任意 i 的二进制表示为 l≤i≤r 时，那么这个子数组就是好数组。

给你一个长度为 n 的数组 a，由从 0 开始的连续非负整数组成，即 ai=i
 为 0≤i≤n-1 (在基于 0 的索引中）。你需要计算这个数组中 k 个好子数组的数量。

由于答案可能非常大，请将其输出为 109+7 模。

输入
每个测试由多个测试用例组成。第一行包含一个整数 t (1≤t≤104) - 测试用例的数量。下面几行描述测试用例。

每个测试用例的单行包含两个整数 n、k（1≤n≤1018,1≤k≤60）。

输出
对于每个测试用例，输出一个整数 - k 个好子数组的数目，模数为 109+7。
 

10
6 1
16 2
1 1
3 1
31 3
14 1
1337 5
100000 20
795569939321040850 56
576460752303423268 59


7
35
1
6
155
8
7323
49965
741136395
66679884


注释
对于第一个测试用例 a=[0,1,2,3,4,5]，k=1。
为了找出答案，让我们用二进制表示法写出所有数字：
a=[000,001,010,011,100,101]

由此可以看出，数字 3 和 5 的二进制表示中有 2≥(k=1)个一。
所以答案应包括所有不包含 3 或 5 的子数组。
的子数组： (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (4, 4).
*/


#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}
